#include <iostream>
#include <queue>

struct Node {
    int val;
    Node *left;
    Node *right;
};

Node *millor(Node *root)
{
    if (root == NULL) {
        return NULL;
    }

    Node *tmp = root->left;
    root->left = millor(root->right);
    root->right = millor(tmp);
    return root;
}

void millor2(Node *root)
{
    std::queue<Node *> q;
    q.push(root);

    while(!q.empty()) {
        Node *parent = q.front();
        q.pop();

        if (parent->left != NULL) {
            q.push(parent->left);
        }

        if (parent->right != NULL) {
            q.push(parent->right);
        }

        Node *tmp = parent->left;
        parent->left = parent->right;
        parent->right = tmp;
    }
}

void link(Node *nodes, int parent, int left, int right)
{
    if (left != -1) {
        nodes[parent].left = &nodes[left];
    }

    if (right != -1) {
        nodes[parent].right = &nodes[right];
    }
}

void in_walk(Node *root)
{
    if (root != NULL) {
        in_walk(root->left);
        std::cout << root->val << " ";
        in_walk(root->right);
    }
}

void print(Node nodes[], int len)
{
    for (int i = 0; i < len; ++i) {
        std::cout << nodes[i].val << " ";
    }

    std::cout << std::endl;
}


int main(int argc, const char *argv[])
{
    Node nodes[7] = {
        {8, NULL, NULL},
        {6, NULL, NULL},
        {10, NULL, NULL},
        {5, NULL, NULL},
        {7, NULL, NULL},
        {9, NULL, NULL},
        {11, NULL, NULL}
    };
    link(nodes, 0, 1, 2);
    link(nodes, 1, 3, 4);
    link(nodes, 2, 5, 6);

    std::cout << "before swap is ";
    in_walk(nodes);
    std::cout << std::endl;

    millor2(nodes);
    std::cout << "after swap is ";
    in_walk(nodes);
    std::cout << std::endl;

    millor(nodes);
    std::cout << "after swap again is ";
    in_walk(nodes);
    std::cout << std::endl;
    return 0;
}
